//Given an integer array nums, in which exactly two elements appear only once an
//d all the other elements appear exactly twice. Find the two elements that appear
// only once. You can return the answer in any order. 
//
// You must write an algorithm that runs in linear runtime complexity and uses o
//nly constant extra space. 
//
// 
// Example 1: 
//
// 
//Input: nums = [1,2,1,3,2,5]
//Output: [3,5]
//Explanation:  [5, 3] is also a valid answer.
// 
//
// Example 2: 
//
// 
//Input: nums = [-1,0]
//Output: [-1,0]
// 
//
// Example 3: 
//
// 
//Input: nums = [0,1]
//Output: [1,0]
// 
//
// 
// Constraints: 
//
// 
// 2 <= nums.length <= 3 * 104 
// -231 <= nums[i] <= 231 - 1 
// Each integer in nums will appear twice, only two integers will appear once. 
// 
// Related Topics 位运算 数组 
// 👍 446 👎 0

package leetcode.editor.cn;
 class P260SingleNumberIii {
    public static void main(String[] args) {
        Solution solution = new P260SingleNumberIii().new Solution();
        solution.singleNumber(new int[]{1, 2, 2, 3, 5, 3});
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public int[] singleNumber(int[] nums) {
            int ret = 0;
            for (int n : nums) {
                ret ^= n;
            }
            int div = 1;
            while ((div & ret) == 0) {
                div <<= 1;
            }
            int a = 0, b = 0;
            for (int n : nums) {
                if ((div & n) != 0) {
                    a ^= n;
                } else {
                    b ^= n;
                }
            }
            return new int[]{a, b};
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}